/**
 * \file   Tas.hpp
 * \author Jonathan BIZET, Mihirai LAU FAT
 *  \version 1.0
 *  \date 4 mars 2012
 */

#ifndef TasERIC_HPP
#define	TasERIC_HPP
#include "math.h"
#include <vector>
#include <assert.h>

/**
 *\class Tas
 *
 * \brief classe permettant de representer un tas binaire
 */
template< class T, class Compare = std::less<T> >
class Tas {
    friend class iterator;
private:
    std::vector<T> *tableau;

    /**
     *Fonction qui renvoit l'indice du fils gauche
     */
    int get_filsg(const int& n);
    /**
     *Fonction qui renvoit l'indice du fils droit
     */
    int get_filsd(const int& n);

    /**
     * Fonction qui renvoit l'indice du peres
     */

    int get_pere(const int& n);
	
	 /**
     * Fonction qui permet de tasser une valeur
     */
    void tasser(const int& indice);
public:
    /**
     * \fn Tas()
     * \brief Constructeur d'un nouveau tas
     */
    Tas();
    /**
     * \fn \~Tas()
     *  \brief Destructeur
     */
    ~Tas();
    /**
     * \fn head()
     * \brief Fonction qui renvoit le tete du tas
     */
    T head() const;
    /**
     * \fn size()
     * \brief Fonction qui permet de recuperer la taille du tas
     */
    size_t size();
    /**
     * \fn add(T uneValeur)
     * \brief Fonction qui permet l'ajout d'un noeud
     * \param uneValeur d'un type generique T
     */
    void add(T uneValeur);
    /**
     * \fn extractMax()
     *  \brief Fonction qui permet d'extraire la tete du tas
     */
    void extractMax();
    /**
     * \fn at(const int i)
     * \brief Fonction qui permet de recuperer la valeur a un indice donnee
     * \param i l'indice de la valeur a recperer
     */
    T at(const int i)const;

    /**
     * \fn at(const int i) const
     *
     * \brief Fonction qui permet de recuperer la valeur a un indice donnee
     *
     * \param i l'indice de la valeur a recperer
     */
    T at(const int i);
    class iterator;

    iterator begin() {
        return iterator(this, 0);
    }

    iterator end() {
        return iterator(this, size());
    }
};

/********************Class Iterator*****************************/
template < class T, class Compare = std::less<T> >
class Tas<T, Compare >::iterator {
    typedef Tas<T, Compare> Tas_;
public:
	
    /**
     * \fn iterator( Tas* t_,int i):indice (i), tas_ (t_)
     * \brief construteur d'iterateur
     * \param t Le tas associer a l'iterateur
     * \param i indice de l'element pointe
     */
    iterator(Tas_* t_, int i) : indice(i), tas_(t_) {
    }
	/**
     * \fn iterator()
     * \brief construteur d'iterateur vide 
      */
	 iterator() {
    }
    /**
     * \fn iterator operator ++()
     * \brief  Surcharge permet de passer a l'element suivant
     */
    iterator operator ++() {
        indice++;
        return (*this);
    }

    /**
     * \fn operator*()
     * \brief Fonction qui permet acceder a l'element point par l'objet
     * \return l'objet pointer par l'iterateur
     */
    T operator*() {
        assert(indice <(int) tas_->size() && tas_ != 0);
        return tas_->at(indice);
    }

    /**
     * \fn operator==()
     * \brief Fonction qui permet de tester l'egalite entre deux iterateurs
     * \param i un autre iterateur
     * \return si i et l'objet this sont egaux la fonction renvoit true sinon false
     */
    bool operator==(const iterator i) {
        return (i.indice == indice) && (tas_ == i.tas_);
    }

    /**
     * \fn operator!=()
     * \brief Fonction qui permet de tester le difference entre deux iterateurs
     * \param i un autre iterateur
     * \return si i et l'objet this sontdifferent a la fonction renvoit true sinon false
     */
    bool operator!=(const iterator i) {
        return !(*this == i);

    }
private:
    int indice;
    Tas_ * tas_;

};

/************************fin class iterator***************************/




template <class T, class Compare>
int Tas<T, Compare>::get_filsg(const int& n) {
    int indice = 2 * n + 1;
    return indice;

}

template <class T, class Compare>
int Tas<T, Compare>::get_filsd(const int& n) {
    int indice = 2 * n + 2;
    return indice;
}

template <class T, class Compare>
int Tas<T, Compare>::get_pere(const int& n) {
    if (n == 1) return 0;
    int indice;
    if (n % 2 == 0)
        indice = floor(n / 2) - 1;
    else
        indice = floor(n / 2);
    return indice;

}

template <class T, class Compare>
Tas<T, Compare>::Tas() {
    tableau = new std::vector<T > ();
}

template <class T, class Compare>
Tas<T, Compare>::~Tas() {
}

template <class T, class Compare>
T Tas<T, Compare>::head() const {
    return tableau->at(0);
}

template <class T, class Compare>
void Tas<T, Compare>::add(T uneValeur) {
    tableau->push_back(uneValeur);
    Compare comp;
    T tmp;
    int indice = tableau->size() - 1;

    while (indice != 0 && get_pere(indice) >= 0 && !comp(tableau->at(indice), tableau->at(get_pere(indice)))) {
        tmp = tableau->at(indice);
        tableau->at(indice) = tableau->at(get_pere(indice));
        tableau->at(get_pere(indice)) = tmp;
        indice = get_pere(indice);

    }
}

template <class T, class Compare >
void Tas<T, Compare>::tasser(const int& indice) {
    if (!tableau->empty()) {
        int g = get_filsg(indice);
        int d = get_filsd(indice);
        int indiceVa;
        indiceVa = tableau->size() - 1;
        int max = indice;
        Compare comp;

        if (g <= tableau->size() - 1) {
            if (comp(tableau->at(g), tableau->at(indice))) {
                max = indice;
            } else {
                max = g;
            }
        }
        if (d <= tableau->size() - 1) {
            if (comp(tableau->at(max), tableau->at(d))) {
                max = d;
            }
        }
        if (max != indice) {

            T tmp = tableau->at(indice);
            tableau->at(indice) = tableau->at(max);
            tableau->at(max) = tmp;
            tasser(max);
        }
    }
}

template <class T, class Compare>
T Tas<T, Compare>::at(const int i) const {

    return tableau->at(i);
}

template <class T, class Compare>
T Tas<T, Compare>::at(const int i) {

    return tableau->at(i);
}

template <class T, class Compare>
void Tas<T, Compare>::extractMax() {
    if (tableau->empty()) {
        return;
    }

    int d = (int) tableau->size() - 1;
    tableau->at(0) = tableau->at(d);
    tableau->pop_back();
    tasser(0);
}

template <class T, class Compare>
size_t Tas<T, Compare>::size() {
    return tableau -> size();
}

#endif	/* TasERIC_HPP */

